Decode String || Surrounded Regions

发表于

Decode String

Question

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

1
2
3
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
Analysis
  • 遇到数字压入栈count中，注意数字可能不止一位
  • 遇到字母衔接到结果字符串res后
  • 遇到[，将当前的结果字符串res压入栈中保存，并且将res置空，方便后续重复字符串的赋值
  • 遇到]，弹出count与str栈顶元素，在str栈顶元素后衔接count个当前的res，最后将所得字符串赋值给res
  • 直接在结果字符串处理，可以方便只有一个的字符串直接衔接在res后
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public String decodeString(String s) {
        String res="";
        int i=0;
        Stack<Integer> cnt=new Stack<>();
        Stack<String> str=new Stack<>();
        char[] strarr=s.toCharArray();
        while(i<s.length()){
            if(Character.isDigit(strarr[i])){
                int num=0;
                while(Character.isDigit(strarr[i])){
                    num=num*10+(strarr[i]-'0');
                    i++;
                }
                cnt.push(num);
            }else if(strarr[i]=='['){
                str.push(res);
                res="";
                i++;
            }else if(strarr[i]==']'){
                int count=cnt.pop();
                StringBuilder strpop=new StringBuilder(str.pop());
                for(int j=0;j<count;j++){
                    strpop.append(res);
                }
                res=strpop.toString();
                i++;
            }else{
                res+=strarr[i];
                i++;
            }
        }
        return res;
    }
}

Surrounded Regions

Question

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X
Analysis

找到位于最外四条边的O，由其出发进行BFS，将该过程中所有遇到的O均改变为#，最后遍历整个方阵。将其中的#改为O，其余的都变为X

  • 用visited实现的方法很蠢，没有意义- -
  • BFS中需要控制边界的条件，首先判断i/j的加一或减一操作后是否会有越界，再分四种状况进行BFS
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Solution {
    public void solve(char[][] board) {
        int row=board.length;
        if(row<2)
            return;
        int col=board[0].length;
        if(col<2)
            return;
        boolean[][] visited=new boolean[row][col];
        for(int i=0;i<row;i++)
            Arrays.fill(visited[i],false);
        for(int i=0;i<row;i++){
            if(board[i][0]=='O'){
                visited[i][0]=true;
                BFS(board,visited,i,0,row,col);
            }
            if(board[i][col-1]=='O'){
                visited[i][col-1]=true;
                BFS(board,visited,i,col-1,row,col);
            }
        }
        for(int j=0;j<col;j++){
            if(board[0][j]=='O'){
                visited[0][j]=true;
                BFS(board,visited,0,j,row,col);
            }
            if(board[row-1][j]=='O'){
                visited[row-1][j]=true;
                BFS(board,visited,row-1,j,row,col);
            }
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(!visited[i][j])
                    board[i][j]='X';
            }
        }
    }
    
    private void BFS(char[][] board, boolean[][] visited, int i, int j, int row, int col){
        if(i>1&&board[i-1][j]=='O'&&!visited[i-1][j]){
            visited[i-1][j]=true;
            BFS(board,visited,i-1,j,row,col);
        }
        if(i<row-1&&board[i+1][j]=='O'&&!visited[i+1][j]){
            visited[i+1][j]=true;
            BFS(board,visited,i+1,j,row,col);
        }
        if(j>1&&board[i][j-1]=='O'&&!visited[i][j-1]){
            visited[i][j-1]=true;
            BFS(board,visited,i,j-1,row,col);
        }
        if(j<col-1&&board[i][j+1]=='O'&&!visited[i][j+1]){
            visited[i][j+1]=true;
            BFS(board,visited,i,j+1,row,col);
        }
    }
}